package com.tgy.leetcode;

import java.util.Arrays;
import java.util.Queue;
import java.util.Stack;

/**
 * @Author: tgy
 * @Date: 12/10/20 2:37 PM
 *
 * https://leetcode-cn.com/problems/longest-palindromic-substring/
 */
public class _5_最长回文子串_01 {

    public String longestPalindrome(String s) {

        if (s == null) {

            return null;
        }

        if (s.length() == 1) {

            return s;
        }

        char[] sChar = s.toCharArray();

        boolean[] dp = new boolean[sChar.length];
        int index=0,len = 1;

        Stack<String> strs = new Stack<>();

        for (int i = sChar.length - 2; i >= 0; i--) {

            dp[i] = true;
            for (int j = sChar.length - 1; j > i ; j--) {

                if (sChar[j] == sChar[i]) {

                    int dis = j - i + 1;

                    if (dis == 2) {

                        dp[j] = true;
                        if (len < dis) {

                            len = dis;
                            index = i;
                        }
                    }else {

                        if (dp[j - 1]) {

                            dp[j] = true;

                            if (len < dis) {

                                len = dis;
                                index = i;
                            }
                        }else {
                            dp[j] = false;
                        }
                    }

                }else {

                    //  这里要重新设置一下，不设置就会存储上一次的值
                    dp[j] = false;
                }
            }
//            System.out.println(Arrays.toString(dp));
            strs.push(Arrays.toString(dp));
        }


        while (!strs.isEmpty()) {

            System.out.println(strs.pop());
        }

        return s.substring(index,index+len);
    }
}
